{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 23.2 The algorithms of Kruskal and Prim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.2-1\n",
    "\n",
    "> Kruskal's algorithm can return different spanning trees for the same input graph $G$, depending on how it breaks ties when the edges are sorted into order. Show that for each minimum spanning tree $T$ of $G$, there is a way to sort the edges of $G$ in Kruskal's algorithm so that the algorithm returns $T$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.2-2\n",
    "\n",
    "> Suppose that we represent the graph $G = (V, E)$ as an adjacency matrix. Give a simple implementation of Prim's algorithm for this case that runs in $O(V^2)$ time."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.2-3\n",
    "\n",
    "> For a sparse graph $G = (V, E)$, where $|E| = \\Theta(V)$, is the implementation of Prim's algorithm with a Fibonacci heap asymptotically faster than the binary-heap implementation? What about for a dense graph, where $|E| = \\Theta(V^2)$? How must the sizes $|E|$ and $|V|$ be related for the Fibonacci-heap implementation to be asymptotically faster than the binary-heap implementation?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Binary-heap: $O(E \\lg V)$ \n",
    "\n",
    "Fibonacci-heap: $O(E + V\\lg V)$\n",
    "\n",
    "* $|E| = \\Theta(V)$\n",
    "\n",
    "Binary-heap: $O(V \\lg V) = O(V \\lg V)$ \n",
    "\n",
    "Fibonacci-heap: $O(E + V\\lg V) = O(V \\lg V)$\n",
    "\n",
    "* $|E| = \\Theta(V^2)$\n",
    "\n",
    "Binary-heap: $O(V^2 \\lg V) = O(V^2 \\lg V)$ \n",
    "\n",
    "Fibonacci-heap: $O(V^2 + V\\lg V) = O(V^2)$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.2-4\n",
    "\n",
    "> Suppose that all edge weights in a graph are integers in the range from $1$ to $|V|$. How fast can you make Kruskal's algorithm run? What if the edge weights are integers in the range from $1$ to $W$ for some constant $W$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $1$ to $|V|$\n",
    "\n",
    "Use counting sort, $O(E \\alpha(V))$.\n",
    "\n",
    "* $1$ to $W$\n",
    "\n",
    "$\\min(O(W + E\\alpha(V)),O(E\\lg V))$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.2-5\n",
    "\n",
    "> Suppose that all edge weights in a graph are integers in the range from $1$ to $|V|$. How fast can you make Prim's algorithm run? What if the edge weights are integers in the range from $1$ to $W$ for some constant $W$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* $1$ to $|V|$\n",
    "\n",
    "Use van Emde Boas trees, $O(E \\lg \\lg V)$.\n",
    "\n",
    "* $1$ to $W$\n",
    "\n",
    "$\\min(O(E\\lg \\lg W), O(E + V \\lg V)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.2-6 $\\star$\n",
    "\n",
    "> Suppose that the edge weights in a graph are uniformly distributed over the halfopen interval $[0, 1)$. Which algorithm, Kruskal's or Prim's, can you make run faster?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.2-7 $\\star$\n",
    "\n",
    "> Suppose that a graph $G$ has a minimum spanning tree already computed. How quickly can we update the minimum spanning tree if we add a new vertex and incident edges to $G$?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$\\dots$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 23.2-8\n",
    "\n",
    "> Professor Borden proposes a new divide-and-conquer algorithm for computing minimum spanning trees, which goes as follows. Given a graph $G = (V, E)$, partition the set $V$ of vertices into two sets $V_1$ and $V_2$ such that $|V_1|$ and $|V_2|$ differ by at most $1$. Let $E_1$ be the set of edges that are incident only on vertices in $V_1$, and let $E_2$ be the set of edges that are incident only on vertices in $V_2$. Recursively solve a minimum-spanning-tree problem on each of the two subgraphs $G_1 = (V_1, E_1)$ and $G_2 = (V_2, E_2)$. Finally, select the minimum-weight edge in $E$ that crosses the cut $(V_1, V_2)$, and use this edge to unite the resulting two minimum spanning trees into a single spanning tree.\n",
    "> \n",
    "> Either argue that the algorithm correctly computes a minimum spanning tree of $G$, or provide an example for which the algorithm fails."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The algorithm fails. Suppose $E = \\{ (u, v), (u, w), (v, w) \\}$, the weight of $(u, v)$ and $(u, w)$ is 1, and the weight of $(v, w)$ is 1000, partition the set into two sets $V_1 = \\{u\\}$ and $V_2 = \\{ v, w \\}$."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
